/**
 * 面试题53-3：数组中数值和下标相等的元素
 * <p>
 * 一个单调递增数组中每个元素都是唯一的，找出数组中任意一个数值等于其下标的元素
 */
public class Offer_53_III {
    /**
     * 方法二：二分查找
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public int numberEqualsIndex(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
                right = mid - 1;
            } else if (nums[mid] < mid) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int numberEqualsIndex1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Offer_53_III solution = new Offer_53_III();
        // 测试 1
        int[] nums1 = { -3, -1, 1, 3, 5 };
        int ans1 = solution.numberEqualsIndex(nums1);
        System.out.println(ans1);
        // 测试 2
        int[] nums2 = { -3, -1, 1, 2, 5 };
        int ans2 = solution.numberEqualsIndex(nums2);
        System.out.println(ans2);
        // 测试 3
        int[] nums3 = { 0, 3, 4, 8, 9 };
        int ans3 = solution.numberEqualsIndex(nums3);
        System.out.println(ans3);
        // 测试 4
        int[] nums4 = { -3, -1, 1, 2, 4 };
        int ans4 = solution.numberEqualsIndex(nums4);
        System.out.println(ans4);
        // 测试 5
        int[] nums5 = { 1 };
        int ans5 = solution.numberEqualsIndex(nums5);
        System.out.println(ans5);
    }
}
